package com.zhugang.week13.tree;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program algorithms
 * @description: BSTree
 * @author: chanzhugang
 * @create: 2022/10/08 16:20
 */
public class BSTree<T extends Comparable<T>> {

    BSTNode<T> root = null;

    static class BSTNode<T> {
        BSTNode<T> left;
        BSTNode<T> right;
        T data;

        public BSTNode(T data) {
            this.data = data;
        }
    }

    /**
     * 添加节点
     *
     * @param element
     */
    public void add(T element) {
        BSTNode<T> node = new BSTNode<>(element);
        if (root == null) {
            root = node;
            return;
        }
        add(root, node);
    }

    private void add(BSTNode<T> node, BSTNode<T> element) {
        if (element.data.compareTo(node.data) <= 0) {
            if (node.left == null) {
                node.left = element;
                return;
            }
            // 递归左子树
            add(node.left, element);
        } else {
            if (node.right == null) {
                node.right = element;
                return;
            }
            // 递归右子树
            add(node.right, element);
        }
    }

    /**
     * 前序遍历
     *
     * @param node
     * @param <T>
     */
    <T> void preOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历
     *
     * @param node
     * @param <T>
     */
    <T> void inOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.data);
        inOrder(node.right);
    }

    /**
     * 后序遍历
     *
     * @param node
     * @param <T>
     */
    <T> void postOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }

    /**
     * 层序遍历：queue
     *
     * @param node
     */
    public <T> void bfs(BSTNode<T> node) {
        Queue<BSTNode<T>> queue = new LinkedList<>();
        queue.add(node);
        while (queue.size() > 0) {
            BSTNode<T> item = queue.poll();
            System.out.println(item.data);
            if (item.left != null) {
                queue.add(item.left);
            }
            if (item.right != null) {
                queue.add(item.right);
            }
        }
    }

    /**
     * 226 翻转二叉树
     * https://leetcode.cn/problems/invert-binary-tree/
     *
     * @param node
     * @param <T>
     */
    public <T> void reverse(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        BSTNode<T> temp = node.left;
        node.left = node.right;
        node.right = temp;

        reverse(node.left);
        reverse(node.right);
    }

    @Test
    public void test() {
        var tree = new BSTree<Integer>();

        tree.add(10);
        tree.add(7);
        tree.add(5);
        tree.add(8);
        tree.add(15);
        tree.add(30);
        tree.add(21);

        var printer = new TreePrinter();
        printer.print(tree.root);

        //  bfs(tree.root);
        // preOrder(tree.root);
        //    postOrder(tree.root);
        inOrder(tree.root);
    }

    @Test
    public void test_reverse() {
        var tree = new BSTree<Integer>();

        tree.add(10);
        tree.add(7);
        tree.add(5);
        tree.add(8);
        tree.add(15);
        tree.add(30);
        tree.add(21);

        var printer = new TreePrinter();
        printer.print(tree.root);

        reverse(tree.root);
        printer.print(tree.root);
    }
}